home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 February: Technology Seed / Mac Tech Seed Feb '97.toast / ODF Release 3 / ODFDev / ODF / Found / FWCollec / SLSrtArr.cpp < prev    next >
Encoding:
Text File  |  1996-12-16  |  8.1 KB  |  308 lines  |  [TEXT/MPS ]
  1. //========================================================================================
  2. //
  3. //    File:                SLSrtArr.cpp
  4. //    Release Version:    $ ODF 3 $
  5. //
  6. //    Copyright:    (c) 1993 - 1996 by Apple Computer, Inc., all rights reserved.
  7. //
  8. //========================================================================================
  9.  
  10. #include "FWFound.hpp"
  11.  
  12. #ifndef SLSRTARR_H
  13. #include "SLSrtArr.h"
  14. #endif
  15.  
  16. #ifndef FWPRIMEM_H
  17. #include "FWPriMem.h"
  18. #endif
  19.  
  20. #ifndef FWMEMMGR_H
  21. #include "FWMemMgr.h"
  22. #endif
  23.  
  24. #ifndef SLMEMMGR_H
  25. #include "SLMemMgr.h"
  26. #endif
  27.  
  28. #ifndef FWPRIDEB_H
  29. #include "FWPriDeb.h"
  30. #endif
  31.  
  32. #ifdef FW_BUILD_MAC
  33. #pragma segment fwcollec
  34. #endif
  35.  
  36. //========================================================================================
  37. // Local constants
  38. //========================================================================================
  39.  
  40. const long kDefaultCapacity = 16;
  41.  
  42. //========================================================================================
  43. // FW_SPrivSortedArray
  44. //========================================================================================
  45.  
  46. struct FW_SPrivSortedArray
  47. {
  48.     void**    fArray;
  49.     long    fLength;
  50.     long    fCapacity;
  51.     FW_SortedArray_CompareFunction    fCompare;
  52. };
  53.  
  54. //========================================================================================
  55. // Global functions
  56. //========================================================================================
  57.  
  58. //----------------------------------------------------------------------------------------
  59. // FW_PrivSortedArray_New
  60. //----------------------------------------------------------------------------------------
  61.  
  62. FW_HSortedArray FW_PrivSortedArray_New(FW_PlatformError* error, FW_SortedArray_CompareFunction compare)
  63. {
  64.     // No try block necessary - Do not throw
  65.     *error = FW_xNoError;
  66.     FW_HSortedArray self = (FW_HSortedArray) FW_PrimitiveAllocateBlock(sizeof(FW_SPrivSortedArray));
  67.     if (!self)
  68.     {
  69.         *error = FW_xMemoryExhausted;
  70.         return NULL;
  71.     }
  72.     self->fArray = (void**) FW_PrimitiveAllocateBlock(sizeof(void*)*kDefaultCapacity);
  73.     if (!self->fArray)
  74.     {
  75.         *error = FW_xMemoryExhausted;
  76.         return NULL;
  77.     }
  78.     self->fLength = 0;
  79.     self->fCapacity = kDefaultCapacity;
  80.     FW_ASSERT(compare != 0);
  81.     self->fCompare = compare;
  82.     
  83.     return self;
  84. }
  85.  
  86. //----------------------------------------------------------------------------------------
  87. // FW_PrivSortedArray_Dispose
  88. //----------------------------------------------------------------------------------------
  89.  
  90. void    FW_PrivSortedArray_Dispose(FW_HSortedArray self)
  91. {
  92.     // No try block necessary - Do not throw
  93.     FW_PrimitiveFreeBlock(self->fArray);
  94.     FW_PrimitiveFreeBlock(self);
  95. }
  96.  
  97. //----------------------------------------------------------------------------------------
  98. // FW_PrivSortedArray_GetLength
  99. //----------------------------------------------------------------------------------------
  100.  
  101. long FW_PrivSortedArray_GetLength(FW_HSortedArray self)
  102. {
  103.     // No try block necessary - Do not throw
  104.     return self->fLength;
  105. }
  106.  
  107. //----------------------------------------------------------------------------------------
  108. // FW_PrivSortedArray_Get
  109. //----------------------------------------------------------------------------------------
  110.  
  111. void* FW_PrivSortedArray_GetItemAt(FW_HSortedArray self, long index)
  112. {
  113.     // No try block necessary - Do not throw
  114.     FW_ASSERT(index <= self->fLength);
  115.     return self->fArray[index];
  116. }
  117.  
  118. //----------------------------------------------------------------------------------------
  119. // FW_PrivSortedArray_Find
  120. //----------------------------------------------------------------------------------------
  121.  
  122. FW_Boolean FW_PrivSortedArray_Find(FW_HSortedArray self, 
  123.                             void* item,
  124.                             long* index)
  125. {
  126.     // No try block necessary - Do not throw
  127.     FW_ASSERT(self->fLength >= 0);
  128.     FW_ASSERT(self->fCapacity >= self->fLength);
  129.  
  130.     *index = 0;
  131.     if (self->fLength == 0)
  132.         return false;
  133.  
  134.     long lo = 0;
  135.     int result = (*self->fCompare)(item, self->fArray[lo]);
  136.     if (result < 0)
  137.         return false;
  138.     if (result == 0)
  139.         return true;
  140.  
  141.     long high = self->fLength - 1;
  142.     *index = high;
  143.     result = (*self->fCompare)(item, self->fArray[high]);
  144.     if (result == 0)
  145.         return true;
  146.     if (result > 0)
  147.     {
  148.         *index = high+1;
  149.         return false;
  150.     }
  151.     
  152.     FW_ASSERT(lo < high);
  153.     FW_ASSERT((*self->fCompare)(item, self->fArray[lo]) > 0);
  154.     FW_ASSERT((*self->fCompare)(item, self->fArray[high]) < 0);
  155.  
  156.     while (lo+1 < high)
  157.     {
  158.         long mid = (lo+high)/2;
  159.         result = (*self->fCompare)(item, self->fArray[mid]);
  160.         if (result == 0)
  161.         {
  162.             *index = mid;
  163.             return true;
  164.         }
  165.         if (result < 0)
  166.         {
  167.             high = mid;
  168.         }
  169.         else
  170.         {
  171.             lo = mid;
  172.         }
  173.  
  174.         FW_ASSERT((*self->fCompare)(item, self->fArray[lo]) > 0);
  175.         FW_ASSERT((*self->fCompare)(item, self->fArray[high]) < 0);
  176.     }
  177.     
  178.     // FW_ASSERT((*self->fCompare)(item, self->fArray[lo]) > 0);
  179.     // FW_ASSERT((*self->fCompare)(item, self->fArray[lo+1]) < 0);
  180.     
  181.     *index = lo+1;
  182.     return false;
  183. }
  184.  
  185. //----------------------------------------------------------------------------------------
  186. // Grow
  187. //----------------------------------------------------------------------------------------
  188.  
  189. static void Grow(FW_HSortedArray self, 
  190.                 FW_PlatformError* error)
  191. {
  192.     // No try block necessary - Do not throw
  193.     *error = 0;
  194.     long newCapacity = self->fCapacity*2;
  195.     self->fArray = (void**) FW_PrimitiveResizeBlock(self->fArray, 
  196.                                                     sizeof(void*)*newCapacity);
  197.     if (self->fArray == 0)
  198.     {
  199.         *error = FW_xMemoryExhausted;
  200.         return;
  201.     }
  202.     self->fCapacity = newCapacity;
  203. }
  204.  
  205. //----------------------------------------------------------------------------------------
  206. // FW_PrivSortedArray_Insert
  207. //----------------------------------------------------------------------------------------
  208.  
  209. void FW_PrivSortedArray_Insert(FW_HSortedArray self, 
  210.                             void* newItem,
  211.                             long index,
  212.                             FW_PlatformError* error)
  213. {
  214.     // No try block necessary - Do not throw
  215.     *error = FW_xNoError;
  216.     FW_ASSERT(self->fLength >= 0);
  217.     FW_ASSERT(self->fCapacity >= self->fLength);
  218.     FW_ASSERT(index >= 0);
  219.     FW_ASSERT(index <= self->fLength);
  220.     
  221.     FW_ASSERT((index==self->fLength) || ((*self->fCompare)(newItem, self->fArray[index]) < 0));
  222.     FW_ASSERT((index==0) || ((*self->fCompare)(newItem, self->fArray[index-1]) > 0));
  223.  
  224.     if (self->fLength == self->fCapacity)
  225.     {
  226.         Grow(self, error);
  227.         if (*error != FW_xNoError)
  228.             return;
  229.     }
  230.     
  231.     FW_PrimitiveCopyMemory(self->fArray + index,
  232.                         self->fArray + index + 1,
  233.                         (self->fLength - index) * sizeof(void*));
  234.     
  235.     self->fArray[index] = newItem;
  236.     ++self->fLength;
  237. }
  238.  
  239. //----------------------------------------------------------------------------------------
  240. // FW_PrivSortedArray_Add
  241. //----------------------------------------------------------------------------------------
  242.  
  243. void FW_PrivSortedArray_Add(FW_HSortedArray self, 
  244.                             void* newItem,
  245.                             long* index,
  246.                             FW_PlatformError* error)
  247. {
  248.     // No try block necessary - Do not throw
  249.     *error = FW_xNoError;
  250.     FW_Boolean result = FW_PrivSortedArray_Find(self, newItem, index);
  251.     FW_ASSERT(!result);
  252.     if (result)
  253.     {
  254.         *error = FW_xBadInsert;
  255.         return;
  256.     }
  257.     FW_PrivSortedArray_Insert(self, newItem, *index, error);
  258.     return;
  259. }
  260.  
  261. //----------------------------------------------------------------------------------------
  262. // FW_PrivSortedArray_RemoveIndex
  263. //----------------------------------------------------------------------------------------
  264.  
  265. void FW_PrivSortedArray_RemoveIndex(FW_HSortedArray self,
  266.                                     long index,
  267.                                     FW_PlatformError* error)
  268. {
  269.     // No try block necessary - Do not throw
  270.     *error = FW_xNoError;
  271.     if (index > (self->fLength - 1))
  272.     {
  273.         *error = FW_xBadRemove;
  274.         return;
  275.     }
  276.     
  277.     --self->fLength;
  278.     
  279.     if (index < self->fLength)
  280.     {
  281.         FW_PrimitiveCopyMemory(self->fArray + index + 1,
  282.                             self->fArray + index,
  283.                             (self->fLength - index) * sizeof(void*));
  284.                             
  285.     }
  286.     return;
  287. }
  288.  
  289. //----------------------------------------------------------------------------------------
  290. // FW_PrivSortedArray_RemoveItem
  291. //----------------------------------------------------------------------------------------
  292.  
  293. void FW_PrivSortedArray_RemoveItem(FW_HSortedArray self,
  294.                                 void* item,
  295.                                 FW_PlatformError* error)
  296. {
  297.     *error = FW_xNoError;
  298.     long index;
  299.     FW_Boolean result = FW_PrivSortedArray_Find(self, item, &index);
  300.     FW_ASSERT(result);
  301.     if (!result)
  302.     {
  303.         *error = FW_xBadRemove;
  304.         return;
  305.     }
  306.     FW_PrivSortedArray_RemoveIndex(self, index, error);
  307.     return;
  308. }